//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTreeSub(preorder,inorder,0,preorder.length-1);
        return root;
    }

    int index;
    private TreeNode buildTreeSub(int[] preorder, int[] inorder, int start, int end) {
        if (end < start) return null;
        int center = findCenter(preorder[index++],inorder);
        TreeNode root = new TreeNode(inorder[center]);
        root.left = buildTreeSub(preorder, inorder, start, center-1);
        root.right = buildTreeSub(preorder, inorder, center+1, end);
        return root;
    }

    private int findCenter(int centerVal, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == centerVal) return i;
        }
        return -1;
    }
}